import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-10 9:22 星期五
 * @motto the harder, the luckier。
 * Completed at @date: 2024-05-13 13:37
 * 首先，定义了一个私有静态的 Map 对象 map，用于存储括号的对应关系。其中，左括号作为 key，右括号作为 value。
 *
 * isValid 方法接收一个字符串 s 作为参数，用于判断该字符串表示的括号序列是否有效。
 *
 * 如果字符串 s 的长度大于 0，并且字符串的第一个字符不在 map 的 key 集合中，则返回 false。这是为了处理特殊情况，如果第一个字符就是右括号，显然括号序列无效。
 *
 * 创建一个 LinkedList 对象 stack，初始化时向其中添加一个特殊字符 '?'，用于处理边界情况。
 *
 * 遍历字符串 s 中的每个字符 c：
 *
 * 如果 map 中包含 c，说明 c 是一个左括号，将其加入栈 stack 中。
 * 否则，c 是一个右括号，需要与栈顶的左括号匹配。如果栈顶元素的对应右括号与 c 不相等，说明括号序列无效，直接返回 false。否则，从栈中移除栈顶元素。
 * 遍历完字符串后，如果栈中只剩下一个元素，说明括号序列有效，返回 true；否则，返回 false。
 *
 * 这个算法利用了栈的特性，通过遍历括号序列并依次将左括号入栈，同时遇到右括号时检查栈顶元素是否与之匹配。如果匹配，则移除栈顶元素；如果不匹配，则直接返回 false。最终，通过检查栈中是否只剩下一个元素来确定括号序列是否有效。
 */

public class _20_IsValid {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
    public boolean isValid2(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.addLast(c);
            else if(map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
    }

    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack[top++] = ')';
            } else if (ch == '[') {
                stack[top++] = ']';
            } else if (ch == '{') {
                stack[top++] = '}';
            } else if (top == 0 || ch != stack[--top]) {
                return false;
            }
        }
        return top == 0;
    }

    //自己写的，s2就通过不了
    public boolean isValid1(String s) {
        char[] s_char = s.toCharArray();
        int a = s_char.length/2;
        boolean vaild = true;
        for (int i = 0; i <a; i++) {
            if((char)(s_char[i] +1)!= s_char[s_char.length-i-1]){
                char w = (char)(s_char[i] +1);
                char e = s_char[s_char.length-i-1];
                boolean d = w!=e;
                vaild = false;
                break;
            }
        }
        return vaild;
    }

    public static void main(String[] args) {
        String s1 = "()";
        String s2 = "()[]{}";
        String s3 = "(]";
        String s4 = "([)]";
        String s5 = "{[]}";
        String s6 = "（{}[)]";
        _20_IsValid isValid = new _20_IsValid();
        System.out.println("s1 是否是有效的括号序列: " + isValid.isValid(s1));
        System.out.println("s2 是否是有效的括号序列: " + isValid.isValid(s2));
        System.out.println("s3 是否是有效的括号序列: " + isValid.isValid(s3));
        System.out.println("s4 是否是有效的括号序列: " + isValid.isValid(s4));
        System.out.println("s5 是否是有效的括号序列: " + isValid.isValid(s5));
        System.out.println("s6 是否是有效的括号序列: " + isValid.isValid(s6));
    }
}
